Comment décrivons-nous mathématiquement les fils invisibles qui relient la société ? Que ce soit les nombres de Bacon reliant Bela Lugosi aux icônes d'Hollywood ou bien les graphes de similarité regroupant des points de données selon leur proximité, la théorie des graphes fournit le langage formel $G = (V, E)$ pour modéliser ces univers discrets.
1. L'anatomie des graphes
Au cœur de tout graphe se trouve un ensemble de sommets ($V$) et un ensemble de arêtes ($E$). Toutefois, les règles d'engagement varient selon la structure :
- Graphe simple : La forme la plus élégante ; elle interdit les boucles (des arêtes reliant un sommet à lui-même) et les arêtes parallèles (des arêtes redondantes entre les mêmes deux points).
- Multigraphe : Permet les boucles et les arêtes parallèles, souvent utilisé pour modéliser plusieurs types d'interactions (par exemple, texte contre appel) entre les mêmes deux nœuds.
- Sommet isolé : Un sommet $v$ est isolé s'il n'est relié à aucune autre arête, représentant un objet sans relations dans l'ensemble actuel.
En science des données, nous utilisons souvent une fonction de dissimilarité pour construire des graphes :
$$s(v, w) = |p_1 - q_1| + |p_2 - q_2| + |p_3 - q_3|$$
Nous traçons une arête entre $v$ et $w$ uniquement si $s(v, w)$ est inférieur à un seuil spécifique, créant ainsi efficacement un réseau de « voisins ».
2. Chemins, connectivité et composantes
Un chemin est une suite de sommets et d'arêtes. Si un chemin ne visite aucun sommet plus d'une fois, il est un chemin simple. La connectivité est le pouls du graphe :
- Graphe connexe : Un chemin existe entre chaque paire de sommets dans le graphe.
- Composantes : Si un graphe n'est pas connexe, il se divise en morceaux disjoints appelés composantes. Chaque composante est un sous-graphe connexe maximal.
3. Sous-graphes : l'architecture des sous-ensembles
Un sous-graphe $G' = (V', E')$ est un sous-ensemble d'un graphe $G$ tel que chaque sommet de $V'$ appartient à $V$, et chaque arête de $E'$ relie des sommets présents dans $V'$. Identifier les sous-graphes est essentiel pour détecter des motifs locaux au sein de réseaux globaux.